1. Technical Field
This invention generally relates to resource management of storage media that are mechanical in nature. More particularly, the present invention relates to an apparatus and method for real time scheduling of prioritized requests for storage media access.
2. Discussion
Storage media resource management is important in many data-intensive applications. For example, disk resource management is an important factor in multimedia applications. Although disk technology continues to improve in speed and storage capacity, the disk bandwidth remains a critical resource in this data-intensive application. Disk technology is currently used to supply digitally stored video-on-demand. Disk technology is also used in multimedia development systems. In applications such as these multimedia applications, data requests typically have strict deadlines. These deadlines are mandated by the application. A video-on-demand system must provide the video data stream without disruptions or delays, as these produce jitter at the user's terminal. Ideally, a storage media access system should timely service all requests, without losing any of them. In reality, at high demand times, some requests may not be serviced on time, and these requests are treated as lost. Preferably, the system should prioritize requests, so that the more important requests (e.g., those paying a higher price) are handled at the expense of lower priority requests.
For example, in a block of MPEG-encoded video data stored in the form of a sequence of I, P and B frames, losing an I data block might result in the loss of more display frames than losing a P or B data block. A disk scheduling algorithm that favors the I frames over the P or B frames may result in better quality of service.
In some data-intensive applications, such as high end multimedia applications, a pricing scheme is used to prioritize data requests. Different priorities are assigned different costs, and the cost to service a data request is generally proportional to the quality of service provided. Users requesting a higher quality of service are expected to be charged more. Quality of service can be quantified in terms of jitter, lost packets, and so forth. One way of honoring different quality of service levels is to prioritize disk requests from each user, based on the pricing package they have subscribed to.
Quality of service is a somewhat more complex issue than simply one of pricing. This is because the user's perception of the quality of service during playback will vary with the medium and format of the material. For example, consider two users, one retrieving an audio stream and the other retrieving a video stream. Both data streams will require periodic disk access requests. If the streams are scheduled in a round robin fashion, disk requests for both streams will need to be serviced with identical deadlines. When the load on the disk access system is sufficiently high, at some point it will not be possible to honor all requests within their respective deadlines. This leads to a delayed (lost) request. Even minute gaps (e.g., hundreds of milliseconds) in the audio data stream will be readily perceived as a noisy, jittering signal; whereas comparable gaps in the video data stream may not even be noticed. This implies that requests for audio data may need to be processed at a higher priority than video data to deliver the same perceived quality of service.
In all of the above cases, deadlines alone are insufficient to model application requirements for media access. Media access scheduling has to be performed with a knowledge of the relative importance of the data to the application. Real time disk scheduling algorithms such as SCAN-EDF, SCAN-RT, etc., assume that all requests have the same priority. Traditionally, multiple priority requests have been handled as follows. A separate queue is maintained for each priority level. Higher priority requests always take precedence over lower priority requests. Lower priority requests can be serviced only if higher priority queues are empty. While this achieves optimal performance for highest priority requests, it usually results in lower disk utilization (lower efficiency), because there is no global optimization of the seek time. Also, low priority requests may starve under the traditional separate queue approach.